{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Convert to Base -2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: baseNeg2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #负二进制转换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，以二进制字符串的形式返回该整数的 <strong>负二进制（<code>base -2</code>）</strong>表示。</p>\n",
    "\n",
    "<p><strong>注意，</strong>除非字符串就是&nbsp;<code>\"0\"</code>，否则返回的字符串中不能含有前导零。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>\"110\"\n",
    "<strong>解释：</strong>(-2)<sup>2</sup> + (-2)<sup>1</sup> = 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>\"111\"\n",
    "<strong>解释：</strong>(-2)<sup>2</sup> + (-2)<sup>1</sup> + (-2)<sup>0</sup> = 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>\"100\"\n",
    "<strong>解释：</strong>(-2)<sup>2</sup> = 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [convert-to-base-2](https://leetcode.cn/problems/convert-to-base-2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [convert-to-base-2](https://leetcode.cn/problems/convert-to-base-2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        ret = []\n",
    "        flag = 0\n",
    "        k = 1\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                ret.append('1')\n",
    "                n -= k\n",
    "            else:\n",
    "                ret.append('0')\n",
    "            n //= 2\n",
    "            k *= -1\n",
    "        return \"\".join(ret[::-1]) or '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "      def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0: return '0'               # 特例\n",
    "        x, y, ans = n, 0, []\n",
    "        while x:\n",
    "            y = x - (((x - 1) // -2) * -2)  # 余数\n",
    "            x = (x - 1) // -2               # 上取整\n",
    "            ans.append(str(y))\n",
    "\n",
    "        return ''.join(ans[::-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return '0'\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        if n & 1 == 1:\n",
    "            return self.baseNeg2((n - 1) // (-2)) + '1'\n",
    "        else:\n",
    "            return self.baseNeg2(n // (-2)) + '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        while n != 0:\n",
    "            x = n & 1\n",
    "            s = str(x) + s\n",
    "            n =n-x\n",
    "            n = n // -2\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        ans = []\n",
    "        while n:\n",
    "            ans.append(str(n % 2))\n",
    "            n = (n - n % 2) // (-2)\n",
    "\n",
    "        return \"\".join(ans[::-1])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        ans = \"\"\n",
    "        while n!=0:\n",
    "            div, mod = divmod(n, -2)\n",
    "            if mod == -1:\n",
    "                mod = 1\n",
    "                div += 1\n",
    "            ans += str(mod)\n",
    "            n = div\n",
    "        return ans[::-1] if ans else \"0\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if not n:\n",
    "            return \"0\"\n",
    "        ans = \"\"\n",
    "        while n!=0:\n",
    "            div, mod = divmod(n, -2)\n",
    "            if mod == -1:\n",
    "                mod = 1\n",
    "                div += 1\n",
    "            ans += str(mod)\n",
    "            n = div\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        while n != 0:\n",
    "            res.append(str(abs(n % -2)))\n",
    "            n = -(n // 2) if n % -2 else n // -2\n",
    "        \n",
    "        res.reverse()\n",
    "        \n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:  return \"0\"\n",
    "\n",
    "        L = R = 1\n",
    "        while R < n:\n",
    "            L = R + 1\n",
    "            R = (4 * (3 * R + 1) - 1) // 3\n",
    "        \n",
    "        ans = [\"1\"]\n",
    "        while L != R:\n",
    "            if len(ans) % 2:\n",
    "                if n < (L + R) / 2:\n",
    "                    ans.append(\"1\")\n",
    "                    R = (L + R) // 2\n",
    "                else:\n",
    "                    ans.append(\"0\")\n",
    "                    L = (L + R) // 2 + 1\n",
    "            elif n > (L + R) / 2:\n",
    "                ans.append(\"1\")\n",
    "                L = (L + R) // 2 + 1\n",
    "            else:\n",
    "                ans.append(\"0\")\n",
    "                R = (L + R) // 2\n",
    "        return \"\".join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    exit()\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/09/18 22:07\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        k = 1\n",
    "        ans = []\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                ans.append('1')\n",
    "                n -= k\n",
    "            else:\n",
    "                ans.append('0')\n",
    "            n //= 2\n",
    "            k *= -1\n",
    "        return ''.join(ans[::-1]) or '0'\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.baseNeg2(self=None, n=4))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        bits = [0] * 32\n",
    "        for i in range(32):\n",
    "            if n == 0:\n",
    "                break\n",
    "            if n & 1:\n",
    "                bits[i] += 1\n",
    "                if i & 1:\n",
    "                    bits[i + 1] += 1\n",
    "            n >>= 1\n",
    "\n",
    "        carry = 0\n",
    "        for i in range(32):\n",
    "            val = carry + bits[i]\n",
    "            bits[i] = val & 1\n",
    "            carry = (val - bits[i]) // -2\n",
    "\n",
    "        pos = 31\n",
    "        res = \"\"\n",
    "        while pos >= 0 and bits[pos] == 0:\n",
    "            pos -= 1\n",
    "        while pos >= 0:\n",
    "            res += str(bits[pos])\n",
    "            pos -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        while n != 0:\n",
    "            x = n & 1\n",
    "            s = str(x) + s\n",
    "            n = n- x\n",
    "            n = n // -2\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        \n",
    "        result = \"\"\n",
    "        while n != 0:\n",
    "            remainder = n % -2\n",
    "            n //= -2\n",
    "\n",
    "            if remainder < 0:\n",
    "                remainder += 2\n",
    "                n += 1\n",
    "            \n",
    "            result = str(remainder) + result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        elif n == 1:\n",
    "            return \"1\"\n",
    "        else:\n",
    "            res = \"\"\n",
    "            while n:\n",
    "                rem = abs(n % -2)\n",
    "                res = str(rem) + res\n",
    "                n -= rem\n",
    "                n //= -2\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0: return '0'\n",
    "        if n == 1: return '1'\n",
    "        if n & 1: return self.baseNeg2((n - 1) // -2) + '1'\n",
    "        return self.baseNeg2(n // -2) + '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n==0:\n",
    "            return \"0\"\n",
    "        # cnt=0\n",
    "        # num=n\n",
    "        # while num>0:\n",
    "        #     num=num//2\n",
    "        #     cnt+=1\n",
    "        # max_i=cnt+1\n",
    "        # @lru_cache\n",
    "        # def dfs(i,res,ans):\n",
    "        #     if  res==n:\n",
    "        #         print(ans)\n",
    "        #         return ans\n",
    "        #     if len(ans)>max_i:\n",
    "        #         return None\n",
    "        #     if res>n:\n",
    "        #         return None\n",
    "        #     pre_ans=ans\n",
    "        #     pre_res=res\n",
    "        #     if i<=max_i:\n",
    "        #         res+=(-2)**(i)\n",
    "        #         ans=\"1\"+ans\n",
    "        #         # print(\"B\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #             return dfs(i+1,res,ans)\n",
    "        #         res=pre_res\n",
    "        #         ans=pre_ans\n",
    "        #         ans=\"0\"+ans\n",
    "        #         # print(\"A\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #              return dfs(i+1,res,ans)\n",
    "        # return dfs(0,0,\"\")\n",
    "        digit = 2\n",
    "        while digit <= n:\n",
    "            if digit & n != 0:\n",
    "                n += digit * 2\n",
    "            digit <<= 2\n",
    "        return bin(n)[2::]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        ans = []\n",
    "        while n:\n",
    "            ans.append(n & 1)\n",
    "            n -= n & 1\n",
    "            n //= -2\n",
    "        \n",
    "        if len(ans) == 0:\n",
    "            ans.append(0)\n",
    "        return \"\".join([str(ans[i]) for i in range(len(ans) - 1, -1, -1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0 :\n",
    "            return '0'\n",
    "        if n == 1 :\n",
    "            return '1'\n",
    "        if n % 2 == 0:\n",
    "            return self.baseNeg2( n // -2) + '0'\n",
    "        else:\n",
    "            return self.baseNeg2((n-1) // -2 ) + '1'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n==0 or n==1:\n",
    "            return str(n)\n",
    "        res=[]\n",
    "        while n:\n",
    "            t=n&1\n",
    "            res.append(str(t))\n",
    "            n-=t\n",
    "            n//=-2\n",
    "        return ''.join(res[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        bits = [0] * 32\n",
    "        for i in range(32):\n",
    "            if n == 0:\n",
    "                break\n",
    "            if n & 1:\n",
    "                bits[i] += 1\n",
    "                if i & 1:\n",
    "                    bits[i + 1] += 1\n",
    "            n >>= 1\n",
    "\n",
    "        carry = 0\n",
    "        for i in range(32):\n",
    "            val = carry + bits[i]\n",
    "            bits[i] = val & 1\n",
    "            carry = (val - bits[i]) // -2\n",
    "\n",
    "        pos = 31\n",
    "        res = \"\"\n",
    "        while pos >= 0 and bits[pos] == 0:\n",
    "            pos -= 1\n",
    "        while pos >= 0:\n",
    "            res += str(bits[pos])\n",
    "            pos -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        return str(n) if n in (0, 1) else self.baseNeg2((n - (n & 1)) // -2) + str(n & 1) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        s = \"\"\n",
    "        while n != 0 and n != 1:\n",
    "            if n%(-2) == 0:\n",
    "                s += \"0\"\n",
    "                n = ceil(n/-2)\n",
    "            else:\n",
    "                s += \"1\"\n",
    "                n = ceil(n/-2)\n",
    "        s += str(n)\n",
    "        a = s[::-1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        bits = [0] * 32\n",
    "        for i in range(32):\n",
    "            if n == 0:\n",
    "                break\n",
    "            if n & 1:\n",
    "                bits[i] += 1\n",
    "                if i & 1:\n",
    "                    bits[i + 1] += 1\n",
    "            n >>= 1\n",
    "\n",
    "        carry = 0\n",
    "        for i in range(32):\n",
    "            val = carry + bits[i]\n",
    "            bits[i] = val & 1\n",
    "            carry = (val - bits[i]) // -2\n",
    "\n",
    "        pos = 31\n",
    "        res = \"\"\n",
    "        while pos >= 0 and bits[pos] == 0:\n",
    "            pos -= 1\n",
    "        while pos >= 0:\n",
    "            res += str(bits[pos])\n",
    "            pos -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        s = \"\"\n",
    "        while n != 0 and n != 1:\n",
    "            if n%(-2) == 0:\n",
    "                s += \"0\"\n",
    "                n = ceil(n/-2)\n",
    "            else:\n",
    "                s += \"1\"\n",
    "                n = ceil(n/-2)\n",
    "        s += str(n)\n",
    "        s = s[::-1]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        ret = []\n",
    "        k = 1\n",
    "        while n:\n",
    "            if n % 2:\n",
    "                ret.append('1')\n",
    "                n -= k\n",
    "            else:\n",
    "                ret.append('0')\n",
    "            n //= 2\n",
    "            k *= -1\n",
    "        return \"\".join(ret[::-1]) or '0'\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        ret = []\n",
    "        while n:\n",
    "            tmp = n % (-2)\n",
    "            ret.append(-tmp)\n",
    "            n = (n + tmp) // (-2)\n",
    "        return ''.join(map(str, ret[::-1])) or '0'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:  return \"0\"\n",
    "\n",
    "        L = R = 1\n",
    "        while R < n:\n",
    "            L = R + 1\n",
    "            R = (4 * (3 * R + 1) - 1) // 3\n",
    "        \n",
    "        ans = [\"1\"]\n",
    "        while L != R:\n",
    "            if len(ans) % 2:\n",
    "                if n < (L + R) / 2:\n",
    "                    ans.append(\"1\")\n",
    "                    R = (L + R) // 2\n",
    "                else:\n",
    "                    ans.append(\"0\")\n",
    "                    L = (L + R) // 2 + 1\n",
    "            elif n > (L + R) / 2:\n",
    "                ans.append(\"1\")\n",
    "                L = (L + R) // 2 + 1\n",
    "            else:\n",
    "                ans.append(\"0\")\n",
    "                R = (L + R) // 2\n",
    "        return \"\".join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        arr = deque()\n",
    "        while n != 0:\n",
    "            d, r = n // -2, n % -2 \n",
    "            if r < 0:\n",
    "                r += 2 \n",
    "                d += 1\n",
    "            arr.appendleft(r)\n",
    "            n = d \n",
    "        return ''.join([str(x) for x in arr])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        return self.baseNeg2Helper(n)\n",
    "\n",
    "    def baseNeg2Helper(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        # Use an iterative approach to construct the base-(-2) representation\n",
    "        result = []\n",
    "        while n != 0:\n",
    "            remainder = n % (-2)\n",
    "            n //= (-2)\n",
    "            if remainder < 0:\n",
    "                remainder += 2\n",
    "                n += 1\n",
    "            result.append(str(remainder))\n",
    "\n",
    "        return \"\".join(result[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n==0:\n",
    "            return \"0\"\n",
    "        # cnt=0\n",
    "        # num=n\n",
    "        # while num>0:\n",
    "        #     num=num//2\n",
    "        #     cnt+=1\n",
    "        # max_i=cnt+1\n",
    "        # @lru_cache\n",
    "        # def dfs(i,res,ans):\n",
    "        #     if  res==n:\n",
    "        #         print(ans)\n",
    "        #         return ans\n",
    "        #     if len(ans)>max_i:\n",
    "        #         return None\n",
    "        #     if res>n:\n",
    "        #         return None\n",
    "        #     pre_ans=ans\n",
    "        #     pre_res=res\n",
    "        #     if i<=max_i:\n",
    "        #         res+=(-2)**(i)\n",
    "        #         ans=\"1\"+ans\n",
    "        #         # print(\"B\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #             return dfs(i+1,res,ans)\n",
    "        #         res=pre_res\n",
    "        #         ans=pre_ans\n",
    "        #         ans=\"0\"+ans\n",
    "        #         # print(\"A\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #              return dfs(i+1,res,ans)\n",
    "        # return dfs(0,0,\"\")\n",
    "        num=n\n",
    "        res=\"\"\n",
    "        while abs(num)>0:\n",
    "            i=num%(-2)\n",
    "            if i==-1:\n",
    "               i=1\n",
    "               num=-(num-1)//(2)\n",
    "            else:\n",
    "                num=num//(-2)\n",
    "            \n",
    "            res=res+str(abs(i))\n",
    "            \n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        ans = []\n",
    "        while n != 0:\n",
    "            r = n % -2\n",
    "            if r == 0:\n",
    "                ans.append(\"0\")\n",
    "            else:\n",
    "                n -= 1\n",
    "                ans.append(\"1\")\n",
    "            n /= -2\n",
    "        \n",
    "        return \"\".join(reversed(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return '0'\n",
    "        if n == 1:\n",
    "            return '1'\n",
    "        if n % 2 == 1:\n",
    "            return self.baseNeg2((n - 1) // -2) + '1'\n",
    "        return self.baseNeg2(n // -2) + '0'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0 or n == 1:\n",
    "            return str(n)\n",
    "        res = []\n",
    "        while n:\n",
    "            remainder = n & 1\n",
    "            res.append(str(remainder))\n",
    "            n -= remainder\n",
    "            n //= -2\n",
    "        return ''.join(res[::-1])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        res=list()\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        while n:\n",
    "            mod = n%(-2)\n",
    "            n//=-2\n",
    "            if mod == -1:\n",
    "                res.append(\"1\")\n",
    "                n+=1\n",
    "            else: \n",
    "                res.append('0')\n",
    "        return ''.join(res[::-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        def getk(n,k):\n",
    "            if n == 0:\n",
    "                return \"0\"\n",
    "            res = \"\"\n",
    "            while n:\n",
    "                a = n%k\n",
    "                if a<0:\n",
    "                    a*=-1\n",
    "                res = str(a) + res\n",
    "                n = (n-a)//k\n",
    "            return res\n",
    "        return getk(n,-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        elif n == 1:\n",
    "            return \"1\"\n",
    "        else:\n",
    "            res = []\n",
    "            while n:\n",
    "                rem = n & 1 #abs(n % -2)\n",
    "                res.insert(0, str(rem))\n",
    "                n -= rem\n",
    "                n //= -2\n",
    "            return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0 or n == 1:\n",
    "            return str(n)\n",
    "        ans = \"\"\n",
    "        while n :\n",
    "            res = n %2\n",
    "            ans += str(res)\n",
    "            n -= res\n",
    "        \n",
    "            n //= -2\n",
    "    \n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def baseNeg2(self, n: int) -> str:\r\n",
    "        if n == 0:\r\n",
    "            return \"0\"\r\n",
    "        elif n == 1:\r\n",
    "            return \"1\"\r\n",
    "        elif n % 2 == 1:\r\n",
    "            a = self.baseNeg2(n - 1)[0:-1]\r\n",
    "            return a + \"1\"\r\n",
    "        else:\r\n",
    "            return self.baseNeg2(n // (-2)) + \"0\"\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        #1 -2 4 -8 16 -32 64 -128 256 -512\n",
    "        maxNeg2 = 0x55555555\n",
    "        diff = maxNeg2 - n\n",
    "        nNeg2 = maxNeg2 ^ diff\n",
    "        if nNeg2 == 0:\n",
    "            return '0'\n",
    "        ans = []\n",
    "        while nNeg2:\n",
    "            ans.append(str(nNeg2 & 1))\n",
    "            nNeg2 >>= 1\n",
    "        return ''.join(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_k_bin_of_n(n, k):\n",
    "    # 整数n的k进制计算（支持正数进制与负数进制）二进制、三进制、十六进制、负进制\n",
    "    if n == 0:\n",
    "        return [0]\n",
    "    if k == 0:\n",
    "        return []\n",
    "    assert abs(k) >= 2  # 原则上要求\n",
    "    # 支持正负数\n",
    "    pos = 1 if k > 0 else -1\n",
    "    k = abs(k)\n",
    "    lst = []  # 0123456789\" + \"\".join(chr(i+ord(\"A\")) for i in range(26))\n",
    "    while n:\n",
    "        lst.append(n % k)\n",
    "        n //= k\n",
    "        n *= pos\n",
    "    lst.reverse()\n",
    "    # 最高支持三十六进制的表达\n",
    "    return lst\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        lst = get_k_bin_of_n(n, -2)\n",
    "        return \"\".join(str(x) for x in lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n <= 1:\n",
    "            return str(n)\n",
    "        res = []\n",
    "        while n != 0:\n",
    "            remainder = n & 1\n",
    "            res.insert(0, str(remainder))\n",
    "            n -= remainder\n",
    "            n //= -2\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, N: int) -> str:\n",
    "        def function(n):\n",
    "            result=\"\"\n",
    "            while True:\n",
    "                result=str(n%2)+result\n",
    "                # print(n % 2)\n",
    "                # print(str(n%2))\n",
    "                t = n/-2\n",
    "                n=math.ceil(n/-2)\n",
    "                print(\"%f, %d\",t, n)\n",
    "                if n==0:\n",
    "                    break\n",
    "            return result\n",
    "        return function(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        return str(n) if n in (0, 1) else self.baseNeg2((n - (n & 1)) // -2) + str(n & 1) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0: return '0'\n",
    "        if n == 1: return '1'\n",
    "        if n & 1: return self.baseNeg2((n - 1) // -2) + '1'\n",
    "        return self.baseNeg2(n // -2) + '0'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        mask = 2\n",
    "        for _ in range(n.bit_length()):\n",
    "            if n & mask:\n",
    "                n += mask << 1\n",
    "            mask <<= 2\n",
    "        return f'{n:b}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n==0:\n",
    "            return \"0\"\n",
    "        # cnt=0\n",
    "        # num=n\n",
    "        # while num>0:\n",
    "        #     num=num//2\n",
    "        #     cnt+=1\n",
    "        # max_i=cnt+1\n",
    "        # @lru_cache\n",
    "        # def dfs(i,res,ans):\n",
    "        #     if  res==n:\n",
    "        #         print(ans)\n",
    "        #         return ans\n",
    "        #     if len(ans)>max_i:\n",
    "        #         return None\n",
    "        #     if res>n:\n",
    "        #         return None\n",
    "        #     pre_ans=ans\n",
    "        #     pre_res=res\n",
    "        #     if i<=max_i:\n",
    "        #         res+=(-2)**(i)\n",
    "        #         ans=\"1\"+ans\n",
    "        #         # print(\"B\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #             return dfs(i+1,res,ans)\n",
    "        #         res=pre_res\n",
    "        #         ans=pre_ans\n",
    "        #         ans=\"0\"+ans\n",
    "        #         # print(\"A\",res,ans)\n",
    "        #         if dfs(i+1,res,ans):\n",
    "        #              return dfs(i+1,res,ans)\n",
    "        # return dfs(0,0,\"\")\n",
    "        num=n\n",
    "        res=\"\"\n",
    "        while abs(num)>0:\n",
    "            i=num%(-2)\n",
    "            if i==-1:\n",
    "               i=1\n",
    "               \n",
    "               num=(num-1)//(-2)\n",
    "            else:\n",
    "                num=num//(-2)\n",
    "            \n",
    "            res=res+str(abs(i))\n",
    "            \n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "        s = \"\"\n",
    "        while n:\n",
    "            remain = n & 1\n",
    "            s = str(remain) + s\n",
    "            n -= remain\n",
    "            n //= -2\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        # Use an iterative approach to construct the base-(-2) representation\n",
    "        result = []\n",
    "        while n != 0:\n",
    "            remainder = n % (-2)\n",
    "            n //= (-2)\n",
    "            if remainder < 0:\n",
    "                remainder += 2\n",
    "                n += 1\n",
    "            result.append(str(remainder))\n",
    "\n",
    "        return \"\".join(result[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return '0'\n",
    "        a = []\n",
    "\n",
    "        while n != 0:\n",
    "            if n % (-2) == 0:\n",
    "                x = n // (-2)\n",
    "            else:\n",
    "                if n - (n + 1) // -2 * (-2) == 1:\n",
    "                    x = (n + 1) // -2\n",
    "                else:\n",
    "                    x = (n - 1) // -2\n",
    "            a.append(n - (-2) * x)\n",
    "            n = x\n",
    "        return ''.join(str(i) for i in a[::-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        \n",
    "        bin_str = list(bin(n)[2:])\n",
    "        l=len(bin_str)\n",
    "        print(bin_str)\n",
    "        sign='0'\n",
    "        i= 1\n",
    "        \n",
    "        while i < l:\n",
    "            tmp = int(sign)+int(bin_str[l-1-i])\n",
    "            if tmp==2:\n",
    "                tmp = 0\n",
    "                sign =1\n",
    "            else:\n",
    "                sign = 0\n",
    "            if i&1==1 and tmp==1:\n",
    "                sign = 1\n",
    "                tmp = 1\n",
    "            bin_str[l-1-i] = str(tmp)\n",
    "            i+=1\n",
    "            #print(bin_str)\n",
    "        if sign==1:\n",
    "            if i&1==1:\n",
    "                bin_str.insert(0,'1')\n",
    "                bin_str.insert(0,'1')\n",
    "            else:\n",
    "                bin_str.insert(0,'1')\n",
    "        print(bin_str)\n",
    "        return \"\".join(bin_str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0:\n",
    "            return \"0\"\n",
    "\n",
    "        ans = \"\"\n",
    "\n",
    "        while n != 0:\n",
    "            c = abs(n % -2)\n",
    "            ans = ('0' if c == 0 else '1') + ans\n",
    "            n = (n - c) // -2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def baseNeg2(self, n: int) -> str:\n",
    "        if n == 0: return '0'\n",
    "        if n == 1: return '1'\n",
    "        if n & 1: return self.baseNeg2((n - 1) // -2) + '1'\n",
    "        return self.baseNeg2(n // -2) + '0'\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
